package Hot100.BackTracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class combinationSum {
    public static void main(String[] args) {
        int[] nums ={2,3,6,7};
        System.out.println(new combinationSum().combinationSum(nums,7));
    }
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backTracking(candidates,target,0,0);
        return result;
    }

    public void backTracking(int[] candidates,int target,int temp,int startIndex){
        if(temp == target){
            result.add(new ArrayList<>(path));
            return;
        } else if (temp > target) {
            return;
        }
        for (int i = startIndex; i <candidates.length ; i++) {
            path.add(candidates[i]);
            backTracking(candidates,target,temp + candidates[i],i);
            path.removeLast();
        }
    }
}
